#ifndef GAMEENGINE_GEOMETRY_POLYGON3D_HPP
#define GAMEENGINE_GEOMETRY_POLYGON3D_HPP

#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

//=================================================================================
// Implementation of the Polygon3d class

//! Default constructor
/*!
 @note Class T should have a default constructor
 */
template <class T>
Polygon3d<T>::Polygon3d() {}

//! Copy constructor
/*!
 @param rhs The triangle to copy
 @note Class T should have a default constructor
 @note Class T should have an assignment operator
 */
template <class T>
Polygon3d<T>::Polygon3d(const Trgl3d<T>& rhs) {
	for ( int k = 0; k < 3; ++k ) {
		points_.push_back(rhs[(Trgl3D::Index)k]);
	}
}

//! Copy constructor
/*!
 @param rhs The triangle to copy
 @note Class T should have a default constructor
 @note Class T should have an assignment operator
 */
template <class T>
Polygon3d<T>::Polygon3d(const Trgl3dFast<T>& rhs) {
	for ( int k = 0; k < 3; ++k ) {
		points_.push_back(rhs[(Trgl3D::Index)k]);
	}
}

//! Copy constructor
/*!
 @param rhs The parallelogram to copy
 @note Class T should have a default constructor
 @note Class T should have an assignment operator
 */
template <class T>
Polygon3d<T>::Polygon3d(const Parallelogram3d<T>& rhs) {
	for ( int k = 0; k < 4; ++k ) {
		points_.push_back(rhs[(Parallelogram3D::Index)k]);
	}
}

//! Destructor
/*!
 @note The destructor of class T should be public
 */
template <class T>
Polygon3d<T>::~Polygon3d() {}

//! Assignment operator
/*!
 @param rhs The triangle to copy
 @note Class T should have an assignment operator
 */
template <class T>
Polygon3d<T>& Polygon3d<T>::operator=(const Polygon3d& rhs) {
	if ( &rhs != this ) {
		points_ = rhs.points_;
	}
	return *this;
}

//! Accessor to the point at given index (read-write, safe)
/*!
 @note This function is secured, but its efficiency is not optimal due to the checking
       on the validity of given index. To get unsafe, but more efficient access, please
	   use the operator[](index) function.
 @param index The index of the point to reach
 @return A pointer to the point to reach (may be nil if no such point exists)
 */
template <class T>
Point3d<T>* Polygon3d<T>::p(PointIndex index) {
	if ( index >= points_.size() ) return nil;
	return &(operator[](index));
}

//! Accessor to the point at given index (read only, safe)
/*!
 @note This function is secured, but its efficiency is not optimal due to the checking
       on the validity of given index. To get unsafe, but more efficient access, please
	   use the operator[](index) function.
 @param index The index of the point to reach
 @return A constant pointer to the point to reach (may be nil if no such point exists)
 */
template <class T>
const Point3d<T>* Polygon3d<T>::p(PointIndex index) const {
	if ( index >= points_.size() ) return nil;
	return &(operator[](index));
}

//! Accessor to the point at given index (read-write, unsafe)
/*!
 @note This function is fast, but not secured - no checking is done on whether there
       actually IS a point at given index, which can result in crashes or memory
	   corruption issues if index is invalid. To get safe access (at the cost of a
	   slight overhead per access), please use the p(index) function.
 @param index The index of the point to reach
 @return A reference to the point to reach
 */
template <class T>
Point3d<T>& Polygon3d<T>::operator[](PointIndex index) {
	return points_[index];
}

//! Accessor to the point at given index (read only, unsafe)
/*!
 @note This function is fast, but not secured - no checking is done on whether there
       actually IS a point at given index, which can result in crashes or memory
	   corruption issues if index is invalid. To get safe access (at the cost of a
	   slight overhead per access), please use the p(index) function.
 @param index The index of the point to reach
 @return A constant reference to the point to reach
 */
template <class T>
const Point3d<T>& Polygon3d<T>::operator[](PointIndex index) const {
	return points_[index];
}

//! Add a point to the polygon
/*!
 @param pt The point to add to the polygon
 @param after_index By default, the point is added at the end of the list of points of
                    the polygon. If after_index is not nil, point is rather added after
					the index pointed by after_index. Please note that even though this
					operation is allowed, point insertion at the beginning of the list
					of points is quite inefficient.
 @return The index where point was added
 */
template <class T>
typename Polygon3d<T>::PointIndex Polygon3d<T>::add_point(const Point3d<T>& pt, PointIndex* after_index) {
	if ( after_index != nil ) {
		if ( (*after_index) <= points_.size() ) {
			std::vector< Point3d<T> >::iterator it = points_.begin();
			for ( PointIndex k = 0; k < (*after_index); ++k ) ++it;
			points_.insert(it, pt);
			return ( (*after_index)+1 );
		}
	}
	points_.push_back(pt);
	return ( points_.size() - 1 );
}

//! Remove given point from the polygon
/*!
 *  This function removes from the polygon all points whose square distance with point
 *  pt is inferior to the given tolerance
 *
 @param pt The point to remove from the polygon
 @param tolerance The geometric tolerance allowed for the square distance of the polygon
                  points and point pt
 @return The number of points that were removed from the polygon
 */
template <class T>
typename Polygon3d<T>::PointCount Polygon3d<T>::remove_point(const Point3d<T>& pt, const T& tolerance) {
	PointCount res = 0;

	// Scan the points of the polygon
	std::vector< Point3d<T> >::iterator it = points_.end(); --it;
	for ( ; it != points_.begin(); --it ) {
		// Check the distance to the target point
		if ( it->get_square_distance(pt) < tolerance ) {
			points_.erase(it);
			++res;
		}
	}
	if ( it->get_square_distance(pt) < tolerance ) {
		points_.erase(it);
		++res;
	}

	// Return the number of removed points
	return res;
}

//! Try to find given point in the polygon
/*!
 *  This function finds the first point in the polygon whose square distance with point
 *  pt is inferior to the given tolerance
 *
 @param pt The point to find the polygon
 @param tolerance The geometric tolerance allowed for the square distance of the polygon
                  points and point pt
 @param from If not nil, only points after the from-th point of the polygon are considered
             in the search (the from-th point being included in this search)
 @return The index of the first point found, if any. If no such point was found, returned
         value is equal to the number of points of the polygon.
 */
template <class T>
typename Polygon3d<T>::PointIndex Polygon3d<T>::find_point(const Point3d<T>& pt, const T& tolerance, PointIndex* from) const {
	// Iterate over the points
	PointIndex res = 0;
	std::vector< Point3d<T> >::const_iterator it = points_.begin();

	// If we should start from a given point, we remove unappropriate points
	if ( from != nil ) {
		for ( ; it != points_.end(); ++it ) {
			if ( res >= (*from) ) break;
		}
	}

	// Iterate over the points of the polygon
	for ( ; it != points_.end(); ++it ) {
		// Check if point fits
		if ( it->get_square_distance(pt) < tolerance ) {
			return res;
		}
		++res;
	}

	// No such point was found
	return points_.size();
}

//! Accessor to the number of points in the polygon
/*!
 @return The number of points in the polygon
 */
template <class T>
typename Polygon3d<T>::PointCount Polygon3d<T>::nb_points() const {
	return points_.size();
}

//! Compute the normal of the polygon
/*!
 @return The normal of the polygon, computed as the normal of the triangle defined
         by the first three points of the polygon. For non-planar polygons, all points
		 after those first three ones are ignored.
 @note This function returns the null vector if the polygon has less than three points
 */
template <class T>
Vector3d<T> Polygon3d<T>::normal() const {
	if ( points_.size() < 3 ) return Vector3d<T>(0,0,0);
	return Vector3d<T>(points_[0], points_[1]).cross( Vector3d<T>(points_[0], points_[2]) ).normalize();
}

//! Compute the perimeter of the polygon
/*!
 @return The perimeter of the polygon
 */
template <class T>
T Polygon3d<T>::perimeter() const {
	T res = (T)0;
	if ( points_.size() == 0 ) return res;

	// Iterate over the polygon points
	std::vector< Point3d<T> >::const_iterator it = points_.begin();
	const Point3d<T>* prev = &(*it); ++it;
	for ( ; it != points_.end(); ++it ) {
		res += it->get_distance(*prev);
		prev = &(*it);
	}
	res += points_.rbegin()->get_distance(*points_.begin());

	// Return the perimeter
	return res;
}

//! Compute the area of the polygon
/*!
 @return The area of the polygon, computed as the sum of the areas of its constituting triangles
 @note This function solely works for convex polygons.
 @todo This limitation is expected to be released in future versions of GameEngine.
 */
template <class T>
T Polygon3d<T>::area() const {
	T res = (T)0;
	if ( points_.size() < 3 ) return res;

	// Iterate over the polygon points
	std::vector< Point3d<T> >::const_iterator it = points_.begin();
	const Point3d<T>* first = &(*it); ++it;
	const Point3d<T>* prev = &(*it); ++it;
	for ( ; it != points_.end(); ++it ) {
		Trgl3dFast<T> trgl(*first, *prev, *it);
		res += trgl.area();
		prev = &(*it);
	}

	// Return the area
	return res;
}

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#endif
